package fun.ipconfig.sort;

/**
 * @author gtinlian
 * 快排实现
 */
public class QuickSort {
    /*当要处理的数字长度小于stackSortLength时使用冒泡*/
    static int stackSortLength = 5;
    /*开启调试打印*/
    public static final boolean DEBUG = false;


    /**
     * 重写快排调用接口
     * 缺点， 针对数据接近有序的数组时性能差，存在栈溢出风险
     * 优点，处理顺序很乱的数组时性能较好，能够根据数据的pivot 去进行数据分段处理
     * @param arr
     */
    public static void sort(int arr[]){
        sort(arr,0,arr.length-1);
    }

    /**
     * 快排中处理重复数据，实现递归调用
     * @param arr
     * @param start
     * @param end
     */
    private static void sort(int []arr, int start, int end){
        if(DEBUG) {
            printArr(arr, start, end, start, true);
        }
        int mid = spit(arr,start, end);
        if(DEBUG) {
            printArr(arr, start, end, mid, false);
            System.out.println();
        }
        if(mid != -1){
            /** 相同的数据*/
            int firstEnd = mid-1;
            int lastStart = mid+1;
            while(firstEnd > start){
                if(arr[mid] == arr[firstEnd-1]){
                    firstEnd--;
                }else{
                    break;
                }
            }
            while(lastStart < end){
                if(arr[mid] == arr[lastStart+1]){
                    lastStart++;
                }else{
                    break;
                }
            }
            if(firstEnd > start) {
                if(DEBUG) {
                    if((mid-1) != firstEnd){
                        System.out.println("pivot 同等值向前移动: " +(mid-1-firstEnd)+"位");
                    }
                }
                sort(arr, start, firstEnd);
            }

            if(lastStart < end) {
                if(DEBUG) {
                    if((mid-1) != firstEnd){
                        System.out.println("pivot 同等值向后移动: " +((lastStart+1)-mid)+"位");
                    }
                }
                sort(arr, lastStart, end);
            }
        }
    }

    /**
     * 数据交换
     * @param arr
     * @param start
     * @param end
     */
    private static void swap(int []arr, int start, int end){
        arr[start] = arr[start] + arr[end];
        arr[end] = arr[start] - arr[end];
        arr[start] = arr[start] - arr[end];
    }

    /**
     * 切割数据
     * @param arr
     * @param start
     * @param end
     * @return
     */
    private static int spit(int []arr, int start, int end){
        int pivot = start;
        if(end-start < 1){
            return -1;
        }
        /* 处理小于stackSortLength的数组时使用冒泡排序*/
        if(end-start < stackSortLength){
            while (true){
                bubbleContinue:
                {
                    for (int i = 0; i < arr.length - 2; i++) {
                        if(arr[i] > arr[i+1]){
                            swap(arr, i, i+1);
                            break bubbleContinue;
                        }
                    }
                    return -1;
                }
            }
        }
        start++;
         for(;end-start > 0;start++){
            if(arr[pivot] < arr[start]){
                for(;end-start > 0;end--){
                    if(arr[pivot] > arr[end]){
                        swap(arr, start, end);
                        break;
                    }
                }
                /* 重合了时返回 */
                if(end-start == 0){
                    start--;
                    if(pivot != start) {
                        swap(arr, pivot, start);
                    }
                    return start;
                }
            }
        }
         /*遍历完成，如果start位置值大于pivot，说明是从后往前遍历完成，那么中间位置在start--处， 如果start位置值小于pivot，说明从前往后遍历完成，那么中间位置在start*/
        if (arr[pivot] < arr[start]){
            start--;
        }
        swap(arr, pivot, start);
        return start;
    }

    /**
     *  打印数字
     * @param arr
     * @param start
     * @param end
     * @param mid
     */
    private static  void printArr(int []arr, int start, int end,int mid,boolean begin){
        if(begin) {
            System.out.println(">>");

        }
        System.out.println("mid: " + mid);

        System.out.print("[ "+arr[start]+" ");
        start++;
        for(;start<=end;start++){

            System.out.print(" , "+arr[start]);
        }
        System.out.print(" ]");
        System.out.println();
        if(!begin){
            System.out.println("<<");
        }
    }

    public static void main(String[] args) {
        int index = 10000;
        int arr[] = new int[index];
        for(int i = 0;i<index;i++){
            arr[i] = i;
        }
        sort(arr,0,arr.length-1);
        for(int i : arr){
            System.out.println(i);
        }
    }
}
